package com.github.yangyishe.p100;

import com.github.yangyishe.TreeNode;

/**
 * 98. 验证二叉搜索树
 * https://leetcode.cn/problems/validate-binary-search-tree/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 *
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [2,1,3]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 *
 *
 * 提示：
 *
 * 树中节点数目范围在[1, 104] 内
 * -231 <= Node.val <= 231 - 1
 */
public class Problem98 {
    public static void main(String[] args) {
        Integer[] arr=new Integer[]{5,1,4,null,null,3,6};
        TreeNode instanceNew = TreeNode.getInstanceNew(arr);

        Problem98 problem98 = new Problem98();
        boolean validBST = problem98.isValidBST(instanceNew);
        System.out.println(validBST);
    }

    /**
     * 思路:
     * bst的基础知识, 中序遍历, 留全局变量lastTmp即可
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {

        return infixOrder(root);
    }

    private Integer lastTmp=null;
    public boolean infixOrder(TreeNode treeNode){
        if(treeNode==null){
            return true;
        }

        boolean left=infixOrder(treeNode.left);
        if(!left){
            return false;
        }

        if(lastTmp!=null){
            if(treeNode.val<=lastTmp){
                return false;
            }
        }
        lastTmp=treeNode.val;

        return infixOrder(treeNode.right);
    }
}
